package solver;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import model.IncrementalCostCalculator;
import model.IncrementalCostCalculatorNoBalance;
import model.IncrementalValidator;
import model.MachineSelector;
import model.Problem;
import model.Solution;
import solver.moves.AbstractMove;
import solver.moves.BestProcessOfMostLoadedMachineToBestMachineMove;
import solver.moves.MathMove;
import solver.moves.RandomMachinePairBestProcessExchangeMove;
import solver.moves.RandomMachinesRandomProcessExchangeMove;
import solver.moves.ServiceCostReducer;
import solver.moves.SingleProcessOfMostLoadedMachineToBestMachineMove;
import solver.moves.SingleRandomProcessToAllMachinesSequential;
import solver.moves.SingleRandomProcessToRandomMachineMove;
import solver.moves.SingleRandomProcessToSeqeuntialMachines;
import solver.moves.WorstMachinePairBestProcessExchange;
import util.Chronograph;
import views.VisualizeJFrame;

import command.Invoker;
import command.MoveProcessToMachineCommand;

public class LateAcceptanceHeuristicSolver extends BaseHeuristicSolver {
	
	// history length. This is a single LAHC parameter. Change it to have
	// different search time.
	int lfa = 1000;
	double minlfaMultiplier = 0.01;
	long initResetLimit= 50000;
	long resetLimit = initResetLimit;
	int minlfa = (int) (0.2 * lfa);
	int v_mult=1;
	// fitness array
	double[] fa;
	
	double init_accel = 0.2;
	double accelerator=init_accel;

	public LateAcceptanceHeuristicSolver(Problem problem,
			Solution initial_solution, Solution current_solution) {
		super(problem, initial_solution, current_solution);
		name = "LateAcceptanceHeuristicSolver";
	}

	public LateAcceptanceHeuristicSolver(Problem problem,
			Solution initial_solution) {
		super(problem, initial_solution);
		name = "LateAcceptanceHeuristicSolver";
	}


//	// performs iternationsNo iterations without examining time
//	public int solveCG(int iterationsNo) {
//		// System.out.printf("Called PA for  %,d iterations\n", iterationsNo);
//		int solution_time = 10; // should be changed
//		lfa = Math.min(solution_time * 100, lfa);
//		minlfa = (int) (0.2 * lfa);
//		Chronograph chrono = new Chronograph();
//		chrono.reset();
//		// int nstep=0; // assigning initial values
//		// int idlestep=0;
//		// double nextCost;
//		int v = 0;
//		// int ie,js;
//		fa = new double[lfa];
//
//		// if(initial_solution==current_solution)
//		// if(!createStartSolution()) // Unable to find a feasible solution
//		// return;
//
//		assert (getFullValidator().getNewSolutionCost() == getCostCalculator().getNewSolutionCost());
//
//		for (int i = 0; i < lfa; i++)
//			fa[i] = best_cost * (1 + (getRandom().nextDouble() * .01)); // Allow
//																	// accept up
//																	// to
//																	// 1+worstFactor
//																	// values
//		setPotentialSolution(getCurrentSolution());
//
//		boolean oldVerbose = Problem.VERBOSE;
//		Problem.VERBOSE = false;
//		int noImprove = 0, iterations = 0;
//		// do // the main search loop is starting here
//		for (int ii = 0; ii < iterationsNo; ii++) {
//			// System.out.println("Old machine balance cost = "+cc.getBalanceCost(current_solution,0));
//			// System.out.println("New machine balance cost = "+cc.getBalanceCost(current_solution,1));
//
//			// if(iterations%100000==49999){
//			// lastMove = mathMove;
//			// mathMove.performMove();
//			// potential_cost = cc.getNewSolutionCost();
//			// potential_solution = iv.getNew_solution();
//			// }
//			// else
//			if (!makeNextMove())
//				continue;
//			iterations++;
//
//			if (potential_cost < current_cost) // checking the acceptance
//												// condition
//			{ // accepting the move
//				if (saveCurrentToBest()) {
//					// System.out.printf("%d:Better cost found %d from %d\n",
//					// iterations, potential_cost,
//					// best_cost);
//				}
//				// current_solution = potential_solution.copy();
//				current_cost = potential_cost;
//
//				// cc.computeCost();
//				// ece.computeCost();
//				// assert(ece.getNewSolutionCost()==cc.getNewSolutionCost()):printCostAnalysis();
//				// assert(ece.getNewSolutionCost()==potential_cost):printCostAnalysis();
//
//				commit();
//				noImprove = 0;
//			} else if (potential_cost <= fa[v]) {// bb.getCachedCost()==localBestCost
//													// ||
//				// current_solution = potential_solution.copy();
//				current_cost = potential_cost;
//
//				// cc.computeCost();
//				// ece.computeCost();
//				// assert(ece.getNewSolutionCost()==cc.getNewSolutionCost());
//				// assert(ece.getNewSolutionCost()==potential_cost):printCostAnalysis();
//
//				commit();
//				noImprove++;
//			} else {
//				// System.out.print("Reject ");
//				undo();
//				noImprove++;
//			}
//
//			if (current_cost < fa[v]) // inserting the current cost into the
//										// fitness array
//				fa[v] = current_cost;
//
//			if (noImprove >= minlfa && minlfa < lfa) {
//				int newMinlfa = minlfa + (int) ((0.1) * lfa);
//				if (newMinlfa > lfa)
//					newMinlfa = lfa;
//				for (int k = 0, i = minlfa; i < newMinlfa; i++, k++)
//					fa[i] = fa[k];
//				minlfa = newMinlfa;
//				noImprove = 0;
//				
//				current_cost = best_cost;
//				env.setCurrentSolution(getBestSolution().copy());
//				
//				resetMoves();
//			}
//
//			// Try to allow worst solution if no progress is happening
//			//
//			// if(idlestep%20000==19999){
//			// System.out.println("Increasing cost. Current "+bb.getCachedCost());
//			// for(int i=0;i<lfa;i++)
//			// fa[i]*=1.01;
//			// }
//			//
//
//			v = (int) (iterations % minlfa); // new virtual beginning of the
//												// fitness array is calculated
//
//			if ((iterations % 100000) == 0) // each 100000 steps we output the
//											// current and the best costs
//			{
////				System.out.printf(
////						"%10d current (%d) best (%d) noImprovement=%d\n",
////						iterations, current_cost, best_cost, noImprove);
//			}
//			chrono.lap();
//		}
//		// } while (noImprove < lfa
//		// && chrono.getElapsedTimeInSeconds() < solution_time);
//		// while ((getNoImprovement()<iterations/100) || (iterations<100000));
//		// // this is the stopping condition
//
//		finishSolution(true);
//
//		return chrono.getElapsedTimeInSeconds();
//	}

	public int solve(int seconds) {
		return solveWithTimeLimit(seconds);
	}
	
	@Override
	public int solveWithTimeLimit(int seconds) {
		MAX_SOLUTION_TIME = seconds;
		startSolution();		
		resetLFA(.01);
		
		int v = 0;
		long lb = env.getProblem().getLowerBound();

		
//		VisualizeJFrame app=new VisualizeJFrame(env.getProblem(), env.getInitialSolution(), 
//				env.getPotentialSolution(), best_cost);
		
		do // the main search loop is starting here
		{
			// System.out.println("Old machine balance cost = "+cc.getBalanceCost(current_solution,0));
			// System.out.println("New machine balance cost = "+cc.getBalanceCost(current_solution,1));

			// if(iterations%100000==49999){
			// lastMove = mathMove;
			// mathMove.performMove();
			// potential_cost = cc.getNewSolutionCost();
			// potential_solution = iv.getNew_solution();
			// }
			// else
			if (!makeNextMove())			
				continue;

			iterations++;
			
//			double lim = (1.0+Math.min(Math.max(noImprove,0)/((double)minlfa)*0.001,0.0001))*fa[v];
//			double lim = fa[(v_mult*v)%minlfa];
			double lim = fa[v];
			
			// checking the acceptance condition
			if (potential_cost < current_cost) 
			{ // accepting the move
				
				if(
						saveCurrentToBest()
				  )
				{
					resetLimit = initResetLimit;
//					app.setCurrentSolution(env.getPotentialSolution());
//					app.setMessage(String.format("%,d", best_cost));
//					app.setCostValue(best_cost);
				}
//				app.setCurrentSolution(env.getPotentialSolution());
//				app.setMessage(String.format("%,d", potential_cost));
//				app.setCostValue(potential_cost);
				
				finishIteration(true, true);
			} else if (potential_cost <= lim) {
				finishIteration(true, false);
//				app.setCurrentSolution(env.getPotentialSolution());
//				app.setMessage(String.format("%,d", potential_cost));
//				app.setCostValue(potential_cost);
			} else {
				finishIteration(false, false);
			}
			
			
			// inserting the current cost into the fitness array
//			if (current_cost < fa[v])
			if (current_cost < lim)
//				fa[v] = current_cost;
			  if(0.999*best_cost>lb)
				  fa[v] =((2.-accelerator)*current_cost+accelerator*best_cost)/2.0;
			  else
				  fa[v] = current_cost; 

			
			if (noImprove >= minlfa && minlfa < lfa) {			
				int newMinlfa = minlfa + (int) ((0.1) * lfa);
				if (newMinlfa > lfa)
					newMinlfa = lfa;
//				System.err.println("Expanding lfa from "+minlfa+" to "+newMinlfa);
				for (int k = 0, i = minlfa; i < newMinlfa; i++, k++)
//					fa[i] = (fa[k]+best_cost)/2;//1.01*//
					fa[i] = ((1.0+env.getRandom().nextInt(5)/1000.0)*fa[k]+best_cost)/2;//1.01*//
//					fa[i] = Math.min(fa[k],(1.0+env.getRandom().nextInt(1)/1000.0)*best_cost);//1.01*//
//					fa[i] = (1+.0001*(k/(double)minlfa))*fa[k];//1.01*//
				minlfa = newMinlfa;
				noImprove = 0;
				v=0;
				current_cost = best_cost;
				env.setCurrentSolution(getBestSolution().copy());
				accelerator=init_accel;
//				resetMoves();
			}

			// Try to allow worst solution if no progress is happening
			//
			// if(idlestep%20000==19999){
			// System.out.println("Increasing cost. Current "+bb.getCachedCost());
			// for(int i=0;i<lfa;i++)
			// fa[i]*=1.01;
			// }
			//

			// new virtual beginning of the fitness array is calculated
			v = (int) (iterations % minlfa); 

			// each 100000 steps we output the current and the best costs
			if ((iterations % 100000) == 0) 										
			{
//				 System.out.printf(
//				 "%10d current (%d) best (%d) noImprovement=%d noBestImprove=%d\n",
//				 iterations, current_cost, best_cost, noImprove, noBestImprove);
//				 System.out.print(vn.toString());
				 accelerator = Math.max(accelerator-0.05, 0);
				 
				 if(noBestImprove>resetLimit){//If we have no real progress for some time
//					 System.err.println("Reseting LFA to higher values");	
//					 if(noBestImprove>5*resetLimit){
//						 setLfa((int)(lfa*1.2));
//						 resetLimit*=2;
//					 }
					 int mult =(int) Math.min(noBestImprove / initResetLimit ,10);
//					 for (int i = 0; i < minlfa; i++)
//						 fa[i] = ((1.0+env.getRandom().nextInt(5)/1000.0)*fa[i]+best_cost)/2;//1.01*//
					 for (int i = 0; i < minlfa; i++)
					     fa[i] = Math.min(fa[i],(1.0+(env.getRandom().nextInt(3*(mult+1))/1000.0))*best_cost); 
//						 fa[i] = (1.0+(env.getRandom().nextInt(3*(mult+1))/1000.0))*best_cost;
					 current_cost = best_cost;
					 env.setCurrentSolution(getBestSolution().copy());
					 noImprove = 0;
//					 minlfa /=2;
					 resetLimit*=2;
				 }
				 
//				 if(resetLimit>5*initResetLimit){
//					System.err.println("*******Reseting random**********");
//					 env.setRandom(new Random(env.getRandom().nextLong()));
//				 }
				 
				 if(1.02*best_cost<current_cost && noBestImprove>10*lfa){//If we have drifted more than 5% reset
//					 System.err.println("Drifted:Reseting to best");
					 noImprove = 0;
//					 noBestImprove=0;
//					 for (int i = 0; i < minlfa; i++)
//							fa[i] = 0.8*best_cost+0.2*fa[i]; 
					 current_cost = best_cost;
					 env.setCurrentSolution(getBestSolution().copy());
//					 minlfa /=2;
				 }
//				 minlfa /=2;
//				 System.err.println("Minlfa="+minlfa);
//				 v_mult = Math.max(1,v_mult-2);				 
			}
			
		} while (
//				noImprove < lfa	&& 
				shouldStop());
		// while ((getNoImprovement()<iterations/100) || (iterations<100000));
		// // this is the stopping condition

		finishSolution(true);
		
//		System.out.print(vn.toString());

		return chrono.getElapsedTimeInSeconds();
	}

	private void resetLFA(double worseFactor){
//		lfa = Math.min(MAX_SOLUTION_TIME * 100, lfa);
//		minlfa = Math.max(200,(int) (0.04 * lfa));
		minlfa = (int) (minlfaMultiplier * lfa);

		fa = new double[lfa];

		for (int i = 0; i < lfa; i++)
			fa[i] = best_cost * (1 + (getRandom().nextDouble() * worseFactor)); // Allow
																	// accept up
																	// to
																	// 1+worstFactor
																	// values
	}
	

	public int getLfa() {
		return lfa;
	}

	public void setLfa(int lfa) {
		this.lfa = lfa;
		minlfa = (int) (minlfaMultiplier * lfa);
		if (fa != null) {
			double[] newfa = new double[lfa];
			int stop = 0;
			if (fa.length < newfa.length)
				stop = fa.length;
			else
				stop = newfa.length;
			for (int i = 0; i < stop; i++) {
				newfa[i] = fa[i];
			}
			fa = newfa;
		}
	}
	
	private boolean stopBasedOnIterations(int iterationsNo){
		return noImprove < lfa && iterations < iterationsNo;
	}
	
	private boolean stopBasedOnTime(){
		return noImprove < lfa && shouldStop();
	}

	@Override
	public void setBestSolution(Solution newSol) {
		super.setBestSolution(newSol);
//		 for(int i=0;i<lfa;i++)
//			 fa[i]*=Math.min((1+getRandom().nextInt(5)*0.01)*best_cost,fa[i]);		
	}

	

}
